package com.recursion;

/**
 * 最大子序列和问题
 * 给定一个序列   a1,a2......an，求其的子序列，该子序列在其所有子序列中，和最大
 *
 *
 *
 */
public class MaxSubSum {

    //自己编写的算法,貌似思路错误？？？的确错了  ！！！！！到时候再来想
    public int maxSumSubSelf(int[] input){

        //记录是否不满足倒序标记或正序标记
        boolean[] descBool = new boolean[input.length];
        boolean[] ascBool = new boolean[input.length];
        //分别记录从某数开始到当前数的和，从某数开始到当前数的和，如果和一直是负数，则认为其是一个子序列标记
        int[] desc = new int[input.length];
        int[] asc = new int[input.length];
        //倒序
        for(int i = input.length - 1; i >= 0; i --){
            int num = input[i];
            for(int j = input.length - 1;j >= i;j -- ){
                if(!descBool[j]){
                    int former = desc[j];
                    int now = former + num;
                    //从j下标的数到当前的数的序列中存在大于0的情况，将其排除
                    if(now >= 0){
                        descBool[j] = true;
                        continue;
                    }
                    desc[j] = now;
                }
            }
        }
        //正序
        for(int i = 0; i <= input.length - 1; i ++){
            int num = input[i];
            for(int j = 0;j <= i;j ++ ){
                if(!ascBool[j]){
                    int former = asc[j];
                    int now = former + num;
                    //从j下标的数到当前的数的序列中存在大于0的情况，将其排除
                    if(now >= 0){
                        ascBool[j] = true;
                        continue;
                    }
                    asc[j] = now;
                }
            }
        }

        int descSign = -1;
        for(int i = descBool.length - 1;i >= 0; i --){
            if(!descBool[i]){
                descSign = i;
                break;
            }
        }

        int ascSign = -1;
        for(int i = 0;i <= ascBool.length - 1; i ++){
            if(!ascBool[i]){
                ascSign = i;
                break;
            }
        }

        int res = 0;

        if(descSign == -1 && ascSign == -1){
            for(int in : input){
                res += in;
            }
            return res;
        }

        if(descSign == -1){
            if(descSign == input.length - 1){
                res = findMax(input);
            }else {
                for (int i = descSign + 1; i <= input.length - 1; i++) {
                    res += input[i];
                }
            }
            return res;
        }

        if(ascSign == -1){
            if(ascSign == 0){
                res = findMax(input);
            }else {
                for (int i = 0; i <= ascSign - 1; i++) {
                    res += input[i];
                }
            }
            return res;
        }

        if(ascSign <= descSign + 1){
            for (int i = descSign + 1; i <= input.length - 1; i++) {
                res += input[i];
            }

            for (int i = 0; i <= ascSign - 1; i++) {
                res += input[i];
            }
        }

        return 0;

    }

    private int findMax(int[] input) {
        return 0;
    }


}
